﻿#define _CRT_SECURE_NO_WARNINGS 1

// 贪心算法

#include <iostream>
using namespace std;

#include <vector>
#include <cmath>
#include <algorithm>

class Solution
{
public:
    int largestSumAfterKNegations(vector<int>& nums, int k)
    {
        int m = 0, minElem = INT_MAX, n = nums.size();
        for (auto x : nums)
        {
            if (x < 0)
                m++;
            minElem = min(minElem, abs(x)); // 求绝对值最⼩的那个数
        }

        // 分类讨论
        int ret = 0;
        if (m > k)
        {
            sort(nums.begin(), nums.end());
            for (int i = 0; i < k; i++) // 前 k ⼩个负数，变成正数
            {
                ret += -nums[i];
            }
            for (int i = k; i < n; i++) // 后面的数不变
            {
                ret += nums[i];
            }
        }

        else
        {
            // 把所有的负数变成正数
            for (auto x : nums)
                ret += abs(x);
            if ((k - m) % 2) // 判断是否处理最⼩的正数
            {
                ret -= minElem * 2;
            }
        }

        return ret;
    }
};

int main()
{
    vector<int> nums = { 4, 2, 3 };

    cout << Solution().largestSumAfterKNegations(nums, 1) << endl;

    return 0;
}